Ilias Diakonikolas

\( \newcommand{\opt}{\mathrm{opt}} \newcommand{\eps}{\epsilon} \newcommand{\R}{\mathbb{R}} \newcommand{\vec}{\mathbf} \newcommand{\wstar}{\w^{\ast}} \newcommand{\x}{\vec x} \newcommand{\w}{\vec w} \newcommand{\wt}{\widetilde} \newcommand{\wh}{\widehat} \newcommand{\poly}{\mathrm{poly}} \newcommand{\polylog}{\mathrm{polylog}} \newcommand{\var}{\mathbf{Var}} \newcommand{\cov}{\mathbf{Cov}} \)
I am the Sheldon B. Lubar professor in the CS department at UW Madison, where I am a member of the theory of computing group, machine learning@uw-madison, and the Institute for Foundations of Data Science. I am also affiliated with the department of Statistics, the Wisconsin Institute for Discovery, and the Data Science Institute.

Prior to joining UW, I was Andrew and Erna Viterbi Early Career Chair in Computer Science at USC, and a faculty member at the University of Edinburgh. Prior to that, I spent two years at UC Berkeley as the Simons Postdoctoral Fellow in Theoretical Computer Science. I obtained my Ph.D. in Computer Science at Columbia University, advised by Mihalis Yannakakis. I did my undergraduate studies in Greece, at the National Technical University of Athens.

Research: My research interests are in algorithms and machine learning. A major goal of my work is to understand the tradeoff between statistical efficiency, computational efficiency, and robustness for fundamental problems in statistics and machine learning. Areas of current focus include high-dimensional robust statistics, information-computation tradeoffs, foundations of deep learning, nonparametric estimation, distribution testing, and data-driven algorithm design. I also have strong interests in applied probability, algorithmic game theory, and their connections to machine learning.

Funding: My research has been supported by an NSF CAREER Award, an NSF Medium Award, an NSF AITF Award, a DARPA grant, an H. I. Romnes Faculty Fellowship, a Sloan Research Fellowship, a Google Faculty Research Award, a Marie Curie Career Integration Grant, and an EPSRC grant.

A short professional biography can be found here.

Interested in working with me? Apply to our Ph.D. program.

University of Wisconsin-Madison
Department of Computer Sciences
1210 W. Dayton St.
Madison, WI 53706
fullname_at_gmail.com

Robust Statistics Book


Expository Articles

Recent Activities


Research Publications [chronologically][by topic]

  1. SoS Certifiability of Subgaussian Distributions and its Algorithmic Applications [abstract] [arxiv]
    I. Diakonikolas, S. Hopkins A. Pensia, S. Tiegel
    Manuscript, 2024

  2. A Near-optimal Algorithm for Learning Margin Halfspaces with Massart Noise
    I. Diakonikolas, N. Zarifis
    Advances in Neural Information Processing Systems (NeurIPS 2024)
    Selected for Spotlight Presentation

  3. Reliable Learning of Halfspaces under Gaussian Marginals
    I. Diakonikolas, L. Ren, N. Zarifis
    Advances in Neural Information Processing Systems (NeurIPS 2024)
    Selected for Spotlight Presentation

  4. Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models [abstract] [arxiv]
    P. Wang, N. Zarifis, I. Diakonikolas, J. Diakonikolas
    Advances in Neural Information Processing Systems (NeurIPS 2024)

  5. Active Learning of General Halfspaces: Label Queries vs Membership Queries
    I. Diakonikolas, D. Kane, M. Ma
    Advances in Neural Information Processing Systems (NeurIPS 2024)

  6. Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise [abstract] [arxiv]
    S. Li, S. Karmalkar, I. Diakonikolas, J. Diakonikolas
    Advances in Neural Information Processing Systems (NeurIPS 2024)

  7. Sum-of-Squares Lower Bounds for Non-Gaussian Component Analysis [abstract] [arxiv]
    I. Diakonikolas, S. Karmalkar, S. Pang, A. Potechin
    Proceedings of the 65th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2024)

  8. Agnostically Learning Multi-index Models with Queries [abstract] [arxiv]
    I. Diakonikolas, D. Kane, V. Kontonis, C. Tzamos, N. Zarifis
    Proceedings of the 65th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2024)
    Invited to SIAM Journal on Computing Special Issue for FOCS 2024

  9. Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation [abstract] [arxiv]
    I. Diakonikolas, D. Kane, J. Lee, T. Pittas
    Proceedings of the 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025)

  10. Fast Co-Training under Weak Dependence via Stream-Based Active Learning [abstract] [proceedings]
    I. Diakonikolas, M. Ma, L. Ren, C. Tzamos
    Proceedings of the 41st International Conference on Machine Learning (ICML 2024)
    Selected for Oral Presentation

  11. Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination [abstract] [arxiv]
    I. Diakonikolas, D. Kane, S. Karmalkar, A. Pensia, T. Pittas
    Proceedings of the 41st International Conference on Machine Learning (ICML 2024)

  12. Robustly Learning Single-Index Models via Alignment Sharpness [abstract] [arxiv]
    N. Zarifis, P. Wang, I. Diakonikolas, J. Diakonikolas
    Proceedings of the 41st International Conference on Machine Learning (ICML 2024)

  13. Testable Learning of General Halfspaces with Adversarial Label Noise [abstract] [arxiv]
    I. Diakonikolas, D. Kane, S. Liu, N. Zarifis
    Proceedings of the 37th Annual Conference on Learning Theory (COLT 2024)

  14. Statistical Query Lower Bounds for Learning Truncated Gaussians [abstract] [arxiv]
    I. Diakonikolas, D. Kane, T. Pittas, N. Zarifis
    Proceedings of the 37th Annual Conference on Learning Theory (COLT 2024)

  15. Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [abstract] [arxiv]
    I. Diakonikolas, D. Kane *Author order randomized
    Proceedings of the 37th Annual Conference on Learning Theory (COLT 2024)

  16. Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs [abstract] [arxiv]
    I. Diakonikolas, D. Kane, V. Kontonis, S. Liu, N. Zarifis
    Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024)

  17. Testing Closeness of Multivariate Distributions via Ramsey Theory [abstract] [arxiv]
    I. Diakonikolas, D. Kane, S. Liu
    Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024)

  18. How Does Wild Data Provably Help OOD Detection? [abstract] [arxiv]
    X. Du, Z. Fang, I. Diakonikolas, Y. Li
    Proceedings of the 12th International Conference on Learning Representations (ICLR 2024)

  19. Online Robust Mean Estimation [abstract] [arxiv]
    D. Kane, I. Diakonikolas, H. Xiao, S. Liu *Author order randomized
    Proceedings of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024)

  20. First Order Stochastic Optimization with Oblivious Noise [abstract] [arxiv]
    I. Diakonikolas, S. Karmalkar, J. Park, C. Tzamos
    Advances in Neural Information Processing Systems (NeurIPS 2023)

  21. SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions [abstract] [arxiv]
    I. Diakonikolas, D. Kane, L. Ren, Y. Sun
    Advances in Neural Information Processing Systems (NeurIPS 2023)

  22. SQ Lower Bounds for Learning Mixtures of Linear Classifiers [abstract] [arxiv]
    I. Diakonikolas, D. Kane, Y. Sun
    Advances in Neural Information Processing Systems (NeurIPS 2023)

  23. Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression [abstract] [arxiv]
    I. Diakonikolas, D. Kane, A. Pensia, T. Pittas
    Advances in Neural Information Processing Systems (NeurIPS 2023)

  24. Robust Second-Order Nonconvex Optimization and Its Application to Low-Rank Matrix Sensing [abstract] [arxiv]
    S. Li, Y. Cheng, I. Diakonikolas, J. Diakonikolas, R. Ge, S. Wright
    Advances in Neural Information Processing Systems (NeurIPS 2023)

  25. Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [abstract] [arxiv]
    I. Diakonikolas, J. Diakonikolas, D. Kane, P. Wang, N. Zarifis
    Advances in Neural Information Processing Systems (NeurIPS 2023)

  26. Efficient Testable Learning of Halfspaces with Adversarial Label Noise [abstract] [arxiv]
    I. Diakonikolas, D. Kane, V. Kontonis, S. Liu, N. Zarifis
    Advances in Neural Information Processing Systems (NeurIPS 2023)

  27. A Spectral Algorithm for List-Decodable Covariance Estimation in Relative Frobenius Norm [abstract] [arxiv]
    I. Diakonikolas, D. Kane, J. Lee, A. Pensia, T. Pittas
    Advances in Neural Information Processing Systems (NeurIPS 2023)
    Selected for Spotlight Presentation

  28. Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions [abstract] [arxiv]
    I. Diakonikolas, S. Karmalkar, J. Park, C. Tzamos
    Proceedings of the 36th Annual Conference on Learning Theory (COLT 2023)

  29. Self-Directed Linear Classification [abstract] [arxiv]
    I. Diakonikolas, V. Kontonis, C. Tzamos, N. Zarifis
    Proceedings of the 36th Annual Conference on Learning Theory (COLT 2023)

  30. Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [abstract] [arxiv]
    I. Diakonikolas, J. Diakonikolas, D. Kane, P. Wang, N. Zarifis
    Proceedings of the 36th Annual Conference on Learning Theory (COLT 2023)

  31. SQ Lower Bounds for Learning Mixtures of Separated and Bounded Covariance Gaussians [abstract] [arxiv]
    I. Diakonikolas, D. Kane, T. Pittas, N. Zarifis
    Proceedings of the 36th Annual Conference on Learning Theory (COLT 2023)

  32. Statistical and Computational Limits for Tensor-on-Tensor Association Detection [abstract] [conference]
    I. Diakonikolas, D. Kane, Y. Luo, A. Zhang
    Proceedings of the 36th Annual Conference on Learning Theory (COLT 2023)

  33. A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points [abstract] [arxiv]
    D. Kane, I. Diakonikolas *Author order randomized
    Proceedings of the 36th Annual Conference on Learning Theory (COLT 2023)

  34. Robustly Learning a Single Neuron via Sharpness [abstract] [arxiv]
    P. Wang, N. Zarifis, I. Diakonikolas, J. Diakonikolas
    Proceedings of the 40th International Conference on Machine Learning (ICML 2023)
    Selected for Oral Presentation

  35. Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals [abstract] [arxiv]
    I. Diakonikolas, D. Kane, L. Ren
    Proceedings of the 40th International Conference on Machine Learning (ICML 2023)

  36. Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA [abstract] [arxiv]
    I. Diakonikolas, D. Kane, A. Pensia, T. Pittas
    Proceedings of the 40th International Conference on Machine Learning (ICML 2023)

  37. A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning [abstract] [arxiv]
    I. Diakonikolas, C. Tzamos, D. Kane *Author order randomized
    Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023)

  38. Gaussian Mean Testing Made Simple [abstract] [arxiv]
    I. Diakonikolas, D. Kane, A. Pensia
    SIAM Symposium on Simplicity in Algorithms (SOSA 2023)

  39. Cryptographic Hardness of Learning Halfspaces with Massart Noise [abstract] [arxiv]
    I. Diakonikolas, D. Kane, P. Manurangsi, L. Ren
    Advances in Neural Information Processing Systems (NeurIPS 2022)

  40. SQ Lower Bounds for Learning Single Neurons with Massart Noise [abstract] [arxiv]
    I. Diakonikolas, D. Kane, L. Ren, Y. Sun
    Advances in Neural Information Processing Systems (NeurIPS 2022)

  41. Nearly-Tight Bounds for Testing Histogram Distributions [abstract] [arxiv]
    C. Canonne, I. Diakonikolas, D. Kane, S. Liu
    Advances in Neural Information Processing Systems (NeurIPS 2022)

  42. Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions [abstract] [arxiv]
    I. Diakonikolas, D. Kane, J. Lee, A. Pensia
    Advances in Neural Information Processing Systems (NeurIPS 2022)

  43. List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [abstract] [arxiv]
    I. Diakonikolas, D. Kane, S. Karmalkar, A. Pensia, T. Pittas
    Advances in Neural Information Processing Systems (NeurIPS 2022)
    Selected for Oral Presentation

  44. Outlier-Robust Sparse Estimation via Non-Convex Optimization [abstract] [arxiv]
    Y. Cheng, I. Diakonikolas, R. Ge, S. Gupta, D. Kane, M. Soltanolkotabi
    Advances in Neural Information Processing Systems (NeurIPS 2022)

  45. Learning General Halfspaces with Adversarial Label Noise via Online Gradient Descent [abstract] [proceedings]
    I. Diakonikolas, V. Kontonis, C. Tzamos, N. Zarifis
    Proceedings of the 39th International Conference on Machine Learning (ICML 2022)

  46. Streaming Algorithms for High-Dimensional Robust Statistics [abstract] [arxiv]
    I. Diakonikolas, D. Kane, A. Pensia, T. Pittas
    Proceedings of the 39th International Conference on Machine Learning (ICML 2022)

  47. Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [abstract] [arxiv]
    I. Diakonikolas, V. Kontonis, C. Tzamos, N. Zarifis
    Proceedings of the 35th Annual Conference on Learning Theory (COLT 2022)

  48. Robust Sparse Mean Estimation via Sum of Squares [abstract] [arxiv]
    I. Diakonikolas, D. Kane, S. Karmalkar, A. Pensia, T. Pittas
    Proceedings of the 35th Annual Conference on Learning Theory (COLT 2022)

  49. Optimal SQ Lower Bounds for Robustly Learning Discrete Product Distributions and Ising Models [abstract] [arxiv]
    I. Diakonikolas, D. Kane, Y. Sun
    Proceedings of the 35th Annual Conference on Learning Theory (COLT 2022)

  50. Non-Gaussian Component Analysis via Lattice Basis Reduction [abstract] [arxiv]
    I. Diakonikolas, D. Kane
    Proceedings of the 35th Annual Conference on Learning Theory (COLT 2022)

  51. Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise [abstract] [arxiv]
    I. Diakonikolas, D. Kane
    Proceedings of the 35th Annual Conference on Learning Theory (COLT 2022)

  52. Learning General Halfspaces with General Massart Noise under the Gaussian Distribution [abstract] [arxiv]
    I. Diakonikolas, D. Kane, V. Kontonis, C. Tzamos, N. Zarifis
    Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC 2022)

  53. Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [abstract] [arxiv]
    I. Diakonikolas, D. M. Kane, D. Kongsgaard, J. Li, K. Tian
    Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC 2022)

  54. Robustly Learning Mixtures of k Arbitrary Gaussians [abstract] [arxiv]
    A. Bakshi, I. Diakonikolas, H. Jia, D. Kane, P. Kothari, S. Vempala
    Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC 2022)

  55. Hardness of Learning a Single Neuron with Adversarial Label Noise [abstract] [proceedings]
    I. Diakonikolas, D. Kane, P. Manurangsi, L. Ren
    Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS 2022)
    Selected for Oral Presentation

  56. Efficient Approximation Algorithms for the Inverse Semivalue Problem [abstract] [proceedings]
    I. Diakonikolas, C. Pavlou, J. Peebles, A. Stewart
    Proceedings of the 21st International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2022)

  57. Forster Decomposition and Learning Halfspaces with Noise [abstract] [arxiv]
    I. Diakonikolas, D. Kane, C. Tzamos
    Advances in Neural Information Processing Systems (NeurIPS 2021)
    Selected for Spotlight Presentation

  58. ReLU Regression with Massart Noise [abstract] [arxiv]
    I. Diakonikolas, J. Park, C. Tzamos
    Advances in Neural Information Processing Systems (NeurIPS 2021)

  59. Statistical Query Lower Bounds for List-Decodable Linear Regression [abstract] [arxiv]
    I. Diakonikolas, D. Kane, A. Pensia, T. Pittas, A. Stewart
    Advances in Neural Information Processing Systems (NeurIPS 2021)
    Selected for Spotlight Presentation

  60. List-Decodable Mean Estimation in Nearly-PCA Time [abstract] [arxiv]
    I. Diakonikolas, D. Kane, D. Kongsgaard, J. Li, K. Tian
    Advances in Neural Information Processing Systems (NeurIPS 2021)
    Selected for Spotlight Presentation

  61. Agnostic Proper Learning of Halfspaces under Gaussian Marginals [abstract] [arxiv]
    I. Diakonikolas, D. Kane, V. Kontonis, C. Tzamos, N. Zarifis
    Proceedings of the 34th Annual Conference on Learning Theory (COLT 2021)

  62. The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals [abstract] [arxiv]
    I. Diakonikolas, D. Kane, T. Pittas, N. Zarifis
    Proceedings of the 34th Annual Conference on Learning Theory (COLT 2021)

  63. Boosting in the Presence of Massart Noise [abstract] [arxiv]
    I. Diakonikolas, R. Impagliazzo, D. M. Kane, R. Lei, J. Sorrell, C. Tzamos
    Proceedings of the 34th Annual Conference on Learning Theory (COLT 2021)

  64. Outlier-Robust Learning of Ising Models Under Dobrushin's Condition [abstract] [arxiv]
    I. Diakonikolas, D. M. Kane, A. Stewart, Y. Sun
    Proceedings of the 34th Annual Conference on Learning Theory (COLT 2021)

  65. The Sample Complexity of Robust Covariance Testing [abstract] [arxiv]
    I. Diakonikolas, D. Kane
    Proceedings of the 34th Annual Conference on Learning Theory (COLT 2021)

  66. Learning Online Algorithms with Distributional Advice [abstract] [proceedings]
    I. Diakonikolas, V. Kontonis, C. Tzamos, A. Vakilian, N. Zarifis
    Proceedings of the 38th International Conference on Machine Learning (ICML 2021)

  67. A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [abstract] [arxiv]
    I. Diakonikolas, D. Kane, V. Kontonis, C. Tzamos, N. Zarifis
    Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC 2021)

  68. Learning Halfspaces with Tsybakov Noise [abstract] [arxiv]
    I. Diakonikolas, V. Kontonis, C. Tzamos, N. Zarifis
    Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC 2021)
    (Conference version to be merged with paper above.)

  69. Optimal Testing of Discrete Distributions with High Probability [abstract] [arxiv]
    I. Diakonikolas, T. Gouleakis, D. Kane, J. Peebles, E. Price
    Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC 2021)

  70. Rapid Approximate Aggregation with Distribution-Sensitive Interval Guarantees [abstract] [arxiv]
    S. Macke, M. Aliakbarpour, I. Diakonikolas, A. Parameswaran, R. Rubinfeld
    Proceedings of the 37th IEEE International Conference on Data Engineering (ICDE 2021)

  71. Outlier Robust Mean Estimation with Subgaussian Rates via Stability [abstract] [arxiv]
    I. Diakonikolas, D. Kane, A. Pensia
    Advances in Neural Information Processing Systems (NeurIPS 2020)

  72. The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise [abstract] [arxiv]
    I. Diakonikolas, D. Kane, P. Manurangsi
    Advances in Neural Information Processing Systems (NeurIPS 2020)

  73. Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [abstract] [arxiv]
    I. Diakonikolas, D. Kane, N. Zarifis
    Advances in Neural Information Processing Systems (NeurIPS 2020)

  74. List-Decodable Mean Estimation via Iterative Multi-Filtering [abstract] [arxiv]
    I. Diakonikolas, D. Kane, D. Kongsgaard
    Advances in Neural Information Processing Systems (NeurIPS 2020)

  75. Non-Convex SGD Learns Halfspaces with Adversarial Label Noise [abstract] [arxiv]
    I. Diakonikolas, V. Kontonis, C. Tzamos, N. Zarifis
    Advances in Neural Information Processing Systems (NeurIPS 2020)

  76. Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [abstract] [arxiv]
    I. Diakonikolas, D. Kane
    Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2020)

  77. Robustly Learning any Clusterable Mixture of Gaussians [abstract] [arxiv]
    I. Diakonikolas, S. Hopkins, D. Kane, S. Karmalkar
    Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2020)
    (Conference version to be merged with this paper)

  78. High-Dimensional Robust Mean Estimation via Gradient Descent [abstract] [arxiv]
    Y. Cheng, I. Diakonikolas, R. Ge, M. Soltanolkotabi
    Proceedings of the 37th International Conference on Machine Learning (ICML 2020)

  79. Efficiently Learning Adversarially Robust Halfspaces with Noise [abstract] [arxiv]
    O. Montasser, S. Goel, I. Diakonikolas, N. Srebro
    Proceedings of the 37th International Conference on Machine Learning (ICML 2020)

  80. Efficient Algorithms for Multidimensional Segmented Regression [abstract] [arxiv]
    I. Diakonikolas, J. Li, A. Voloshinov
    Manuscript, 2020

  81. Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [abstract] [arxiv]
    I. Diakonikolas, D. Kane, V. Kontonis, N. Zarifis
    Proceedings of the 33rd Annual Conference on Learning Theory (COLT 2020)

  82. Approximation Schemes for ReLU Regression [abstract] [arxiv]
    I. Diakonikolas, S. Goel, S. Karmalkar, A. Klivans, M. Soltanolkotabi
    Proceedings of the 33rd Annual Conference on Learning Theory (COLT 2020)

  83. Learning Halfspaces with Massart Noise Under Structured Distributions [abstract] [arxiv]
    I. Diakonikolas, V. Kontonis, C. Tzamos, N. Zarifis
    Proceedings of the 33rd Annual Conference on Learning Theory (COLT 2020)

  84. Private Testing of Distributions via Sample Permutations [abstract] [proceedings]
    M. Aliakbarpour, I. Diakonikolas, D. Kane, R. Rubinfeld
    Advances in Neural Information Processing Systems (NeurIPS 2019)

  85. Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin [abstract] [arxiv]
    I. Diakonikolas, D. Kane, P. Manurangsi
    Advances in Neural Information Processing Systems (NeurIPS 2019)
    Selected for Spotlight Presentation at NeurIPS 2019

  86. Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering [abstract] [arxiv]
    I. Diakonikolas, S. Karmalkar, D. Kane, E. Price, A. Stewart
    Advances in Neural Information Processing Systems (NeurIPS 2019)

  87. Distribution-Independent PAC Learning of Halfspaces with Massart Noise [abstract] [arxiv]
    I. Diakonikolas, T. Gouleakis, C. Tzamos
    Advances in Neural Information Processing Systems (NeurIPS 2019)
    Outstanding Paper Award at NeurIPS 2019
    See here
    for a description of our work by the program chairs and here
    for the slides of my NeurIPS talk.

  88. Equipping Experts/Bandits with Long-term Memory [abstract] [arxiv]
    K. Zheng, H. Luo, I. Diakonikolas, L. Wang
    Advances in Neural Information Processing Systems (NeurIPS 2019)

  89. A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families [abstract] [arxiv]
    B. Axelrod, I. Diakonikolas, A. Sidiropoulos, A. Stewart, G. Valiant
    Advances in Neural Information Processing Systems (NeurIPS 2019)

  90. Faster Algorithms for High-Dimensional Robust Covariance Estimation [abstract] [arxiv]
    Y. Cheng, I. Diakonikolas, R. Ge, D. Woodruff
    Proceedings of the 32nd Annual Conference on Learning Theory (COLT 2019)

  91. Communication and Memory Efficient Testing of Discrete Distributions [abstract] [arxiv]
    I. Diakonikolas, T. Gouleakis, D. Kane, S. Rao
    Proceedings of the 32nd Annual Conference on Learning Theory (COLT 2019)

  92. Testing Identity of Multidimensional Histograms [abstract] [arxiv]
    I. Diakonikolas, D. Kane, J. Peebles
    Proceedings of the 32nd Annual Conference on Learning Theory (COLT 2019)

  93. Sever: A Robust Meta-Algorithm for Stochastic Optimization [abstract] [arxiv] [code]
    I. Diakonikolas, G. Kamath, D. Kane, J. Li, J. Steinhardt, A. Stewart
    Proceedings of the 36th International Conference on Machine Learning (ICML 2019)
    Oral Presentation at the NeurIPS 2018 Workshop on Security in Machine Learning (SECML 2018)

  94. Degree-d Chow Parameters Robustly Determine Degree-d PTFs (and Algorithmic Applications) [abstract] [eccc]
    I. Diakonikolas, D. Kane
    Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC 2019)

  95. Efficient Robust Proper Learning of Log-concave Distributions [abstract] [arxiv]
    I. Diakonikolas, D. Kane, A. Stewart
    Manuscript

  96. On the Complexity of the Inverse Semivalue Problem for Weighted Voting Games [abstract] [arxiv]
    I. Diakonikolas, C. Pavlou
    Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI 2019)

  97. Collision-based Testers are Optimal for Uniformity and Closeness [abstract] [eccc]
    I. Diakonikolas, T. Gouleakis, J. Peebles, E. Price
    Chicago Journal of Theoretical Computer Science, 2019
    Also see Oded Goldreich's exposition of our proof here

  98. High-Dimensional Robust Mean Estimation in Nearly-Linear Time [abstract] [arxiv]
    Y. Cheng, I. Diakonikolas, R. Ge
    Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)

  99. Efficient Algorithms and Lower Bounds for Robust Linear Regression [abstract] [arxiv]
    I. Diakonikolas, W. Kong, A. Stewart
    Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)

  100. Fourier-based Testing for Families of Distributions [abstract] [eccc]
    C. Canonne, I. Diakonikolas, A. Stewart
    Advances in Neural Information Processing Systems (NeurIPS 2018)

  101. Sharp Bounds for Generalized Uniformity Testing [abstract] [arxiv]
    I. Diakonikolas, D. Kane, A. Stewart
    Advances in Neural Information Processing Systems (NeurIPS 2018)
    Selected for Spotlight Presentation at NeurIPS 2018
    See the comments in Oded Goldreich's Choices #229

  102. Robust Learning of Fixed-Structure Bayesian Networks [abstract] [arxiv]
    Y. Cheng, I. Diakonikolas, D. Kane, A. Stewart
    Advances in Neural Information Processing Systems (NeurIPS 2018)

  103. Differentially Private Identity and Closeness Testing of Discrete Distributions [abstract] [arxiv]
    M. Aliakbarpour, I. Diakonikolas, R. Rubinfeld
    Proceedings of the 35th International Conference on Machine Learning (ICML 2018)

  104. Near-Optimal Sample Complexity Bounds for Maximum Likelihood Estimation of Multivariate Log-concave Densities [abstract] [arxiv]
    T. Carpenter, I. Diakonikolas, A. Sidiropoulos, A. Stewart
    Proceedings of the 31st Annual Conference on Learning Theory (COLT 2018)

  105. Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms [abstract] [arxiv]
    I. Diakonikolas, J. Li, L. Schmidt
    Proceedings of the 31st Annual Conference on Learning Theory (COLT 2018)

  106. Sample-Optimal Identity Testing with High Probability [abstract] [arxiv]
    I. Diakonikolas, T. Gouleakis, J. Peebles, E. Price
    Proceedings of the 45th Intl. Colloquium on Automata, Languages and Programming (ICALP 2018)
    See the comments in Oded Goldreich's Choices #229

  107. Testing Conditional Independence of Discrete Distributions [abstract] [arxiv]
    C. Canonne, I. Diakonikolas, D. Kane, A. Stewart
    Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC 2018)

  108. List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussians [abstract] [arxiv]
    I. Diakonikolas, D. Kane, A. Stewart
    Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC 2018)

  109. Learning Geometric Concepts with Nasty Noise [abstract] [arxiv]
    I. Diakonikolas, D. Kane, A. Stewart
    Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC 2018)

  110. Robustly Learning a Gaussian: Getting Optimal Error, Efficiently [abstract] [arxiv]
    I. Diakonikolas, G. Kamath, D. Kane, J. Li, A. Moitra, A. Stewart
    Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018)

  111. Communication-Efficient Distributed Learning of Discrete Distributions [abstract] [proceedings]
    I. Diakonikolas, E. Grigorescu, J. Li, A. Natarajan, K. Onak, L. Schmidt
    Advances in Neural Information Processing Systems (NIPS 2017)
    Selected for Oral Presentation at NIPS 2017

  112. Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures [abstract] [eccc] [arxiv]
    I. Diakonikolas, D. Kane, A. Stewart
    Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017)
    See here and here for videos of related talks.

  113. Being Robust (in High Dimensions) Can be Practical [abstract] [arxiv] [code]
    I. Diakonikolas, G. Kamath, D. Kane, J. Li, A. Moitra, A. Stewart
    Proceedings of the 34th International Conference on Machine Learning (ICML 2017)

  114. Testing Bayesian Networks [abstract] [arxiv]
    C. Canonne, I. Diakonikolas, D. Kane, A. Stewart
    Proceedings of the 30th Annual Conference on Learning Theory (COLT 2017)
    Journal version in IEEE Transactions on Information Theory, to appear.

  115. Learning Multivariate Log-concave Distributions [abstract] [arxiv]
    I. Diakonikolas, D. Kane, A. Stewart
    Proceedings of the 30th Annual Conference on Learning Theory (COLT 2017)

  116. Near-optimal Closeness Testing of Discrete Histogram Distributions [abstract] [arxiv]
    I. Diakonikolas, D. Kane, V. Nikishkin
    Proceedings of the 44th Intl. Colloquium on Automata, Languages and Programming (ICALP 2017)

  117. Playing Anonymous Games using Simple Strategies [abstract] [arxiv]
    Y. Cheng, I. Diakonikolas, A. Stewart
    Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)

  118. Sample Optimal Density Estimation in Nearly-Linear Time [abstract] [pdf] [code]
    J. Acharya, I. Diakonikolas, J. Li, L. Schmidt
    Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017)

  119. Robust Estimators in High Dimensions without the Computational Intractability [abstract] [arxiv]
    I. Diakonikolas, G. Kamath, D. Kane, J. Li, A. Moitra, A. Stewart
    Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016)
    SIAM Journal on Computing Special Issue for FOCS 2016
    Invited to Communications of the ACM, Research Highlights
    See here for my Simons Institute tutorial on the topic and here for a previous related talk.

  120. A New Approach for Testing Properties of Discrete Distributions [abstract] [pdf] [arxiv]
    I. Diakonikolas, D. Kane
    Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016)
    Also see the comments in Oded Goldreich's Choices #188 and #195, and Oded's very nice exposition of our framework here

  121. Fast Algorithms for Segmented Regression [abstract] [pdf] [code]
    J. Acharya, I. Diakonikolas, J. Li, L. Schmidt
    Proceedings of the 33rd International Conference on Machine Learning (ICML 2016)

  122. Properly Learning Poisson Binomial Distributions in Almost Polynomial Time [abstract] [pdf] [arxiv]
    I. Diakonikolas, D. Kane, A. Stewart
    Proceedings of the 29th Annual Conference on Learning Theory (COLT 2016)

  123. Optimal Learning via the Fourier Transform for Sums of Independent Integer Random Variables [abstract] [pdf] [arxiv] [notes]
    I. Diakonikolas, D. Kane, A. Stewart
    Proceedings of the 29th Annual Conference on Learning Theory (COLT 2016)

  124. The Fourier Transform of Poisson Multinomial Distributions and its Algorithmic Applications [abstract] [pdf] [arxiv]
    I. Diakonikolas, D. Kane, A. Stewart
    Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC 2016)

  125. Testing Shape Restrictions of Discrete Distributions [abstract] [pdf]
    C. Canonne, I. Diakonikolas, T. Gouleakis, R. Rubinfeld
    Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science (STACS 2016)
    Invited to Special Issue for STACS 2016

  126. Differentially Private Learning of Structured Discrete Distributions [abstract] [pdf] [code]
    I. Diakonikolas, M. Hardt, L. Schmidt
    Advances in Neural Information Processing Systems (NIPS 2015)

  127. Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions [abstract] [pdf]
    I. Diakonikolas, D. Kane, V. Nikishkin
    Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015)

  128. On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms [abstract] [pdf]
    X. Chen, I. Diakonikolas, A. Orfanou, D. Paparas, X. Sun, M. Yannakakis
    Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015)

  129. Fast and Near-Optimal Algorithms for Approximating Distributions by Histograms [abstract] [pdf]
    J. Acharya, I. Diakonikolas, C. Hegde, J. Li, L. Schmidt
    Proceedings of the 34th Annual ACM Symposium on Principles of Database Systems (PODS 2015)

  130. Testing Identity of Structured Distributions [abstract] [pdf]
    I. Diakonikolas, D. Kane, V. Nikishkin
    Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015)

  131. Learning from Satisfying Assignments [abstract] [pdf]
    A. De, I. Diakonikolas, R. Servedio
    Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015)

  132. Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms [abstract] [pdf]
    S. Chan, I. Diakonikolas, R. Servedio, X. Sun
    Advances in Neural Information Processing Systems (NIPS 2014)

  133. Efficient Density Estimation via Piecewise Polynomial Approximation [abstract] [pdf]
    S. Chan, I. Diakonikolas, R. Servedio, X. Sun
    Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014)

  134. Deterministic Approximate Counting for Juntas of Degree-$2$ Polynomial Threshold Functions [abstract] [pdf]
    A. De, I. Diakonikolas, R. Servedio
    Proceedings of the 29th Annual IEEE Conference on Computational Complexity (CCC 2014)

  135. The Complexity of Optimal Multidimensional Pricing [abstract] [pdf]
    X. Chen, I. Diakonikolas, D. Paparas, X. Sun, M. Yannakakis
    Games and Economic Behavior, accepted with minor revisions
    Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014)

  136. Optimal Algorithms for Testing Closeness of Discrete Distributions [abstract] [pdf]
    S. Chan, I. Diakonikolas, G. Valiant, P. Valiant
    Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014)
    Blog post about this work: Property Testing Review

  137. A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage [abstract] [pdf]
    C. Daskalakis, A. De, I. Diakonikolas, A. Moitra, R. Servedio
    Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014)
    Featured in Abstract Talk. Podcast is here

  138. Learning Sums of Independent Integer Random Variables [abstract] [pdf]
    C. Daskalakis, I. Diakonikolas, R. O'Donnell, R. Servedio, L-Y. Tan
    Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013)
    Blog post about this work: MIT theory student blog

  139. Deterministic Approximate Counting for Degree-$2$ Polynomial Threshold Functions [abstract] [pdf]
    A. De, I. Diakonikolas, R. Servedio
    Manuscript, 2013. Available as ECCC technical report [link]

  140. A robust Khintchine Inequality and computing optimal constants in Fourier analysis and high-dimensional geometry [abstract] [pdf]
    A. De, I. Diakonikolas, R. Servedio
    SIAM Journal on Discrete Mathematics, 30-2 (2016), pp. 1058-1094
    Proceedings of the 40th Intl. Colloquium on Automata, Languages and Programming (ICALP 2013)

  141. Learning Mixtures of Structured Distributions over Discrete Domains [abstract] [pdf]
    S. Chan, I. Diakonikolas, R. Servedio, X. Sun
    Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)

  142. Testing $k$-modal Distributions: Optimal Algorithms via Reductions [abstract] [pdf]
    C. Daskalakis, I. Diakonikolas, R. Servedio, G. Valiant, P. Valiant
    Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)

  143. An Optimal Algorithm for the Efficient Approximation of Convex Pareto Curves
    I. Diakonikolas, M. Yannakakis
    Manuscript, 2012

  144. Efficiency-Revenue Tradeoffs in Auctions [abstract] [pdf]
    I. Diakonikolas, C.H. Papadimitriou, G. Pierrakos, Y. Singer
    Proceedings of the 39th Intl. Colloquium on Automata, Languages and Programming (ICALP 2012)

  145. The Inverse Shapley Value Problem [abstract] [pdf]
    A. De, I. Diakonikolas, R. Servedio
    Games and Economic Behavior, accepted with minor revisions
    Proceedings of the 39th Intl. Colloquium on Automata, Languages and Programming (ICALP 2012)

  146. Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces [abstract] [pdf]
    A. De, I. Diakonikolas, V. Feldman, R. Servedio
    Journal of the ACM, 61(2), 2014. Invited to Theory of Computing special issue on Analysis of Boolean functions (declined)
    Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC 2012)
    IBM Research 2014 Pat Goldberg Math/CS/EE Best Paper Award

  147. Learning Poisson Binomial distributions [abstract] [pdf]
    C. Daskalakis, I. Diakonikolas, R. Servedio
    Invited to Algorithmica special issue on New Theoretical Challenges in Machine Learning
    Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC 2012)

  148. Learning $k$-modal distributions via testing [abstract] [pdf]
    C. Daskalakis, I. Diakonikolas, R. Servedio
    Theory of Computing, 10 (20), 535-570 (2014)
    Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012)
    Oded Goldreich's Choices #72

  149. Noise Stable Halfspaces are Close to Very Small Juntas [abstract] [pdf]
    I. Diakonikolas, R. Jaiswal, R. Servedio, L.-Y.Tan, A. Wan
    Chicago Journal of Theoretical Computer Science, 2015

  150. Supervised Design Space Exploration by Compositional Approximation of Pareto sets [abstract] [pdf]
    H.-Y. Liu, I. Diakonikolas, M. Petracca, L.P. Carloni
    Proceedings of the 48th Design Automation Conference (DAC 2011)

  151. Disjoint-Path Facility Location: Theory and Practice [abstract] [pdf]
    L. Breslau, I. Diakonikolas, N. Duffield, Y.Gu, M.T. Hajiaghayi, D.S. Johnson, H. Karloff, M. Resende, S.Sen
    Proceedings of the 13th Workshop on Algorithm Engineering and Experiments (ALENEX 2011)
    Journal version in Operations Research, 2019 [arxiv]

  152. Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions [abstract] [pdf]
    I. Diakonikolas, R. O'Donnell, R. Servedio, Y.Wu
    Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011)

  153. Bounded Independence Fools Degree-$2$ Threshold Functions [abstract] [pdf]
    I. Diakonikolas, D. Kane, J. Nelson
    Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010)

  154. Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions [abstract] [pdf]
    I. Diakonikolas, P. Raghavendra, R. Servedio, L.-Y. Tan
    SIAM Journal on Computing, 43(1), 231-253 (2014)
    Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC 2010)
    (Conference version merged with this paper by Harsha, Klivans and Meka)

  155. A Regularity Lemma, and Low-weight Approximators, for low-degree Polynomial Threshold Functions [abstract] [pdf]
    I. Diakonikolas, R. Servedio, L.-Y. Tan, A. Wan
    Theory of Computing, 10(2), 27-53 (2014)
    Proceedings of the 25th Annual IEEE Conference on Computational Complexity (CCC 2010)

  156. How Good is the Chord Algorithm? [abstract] [pdf]
    C. Daskalakis, I. Diakonikolas, M. Yannakakis
    SIAM Journal on Computing, 45(3), pp. 811-858, 2016
    Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)

  157. Bounded Independence Fools Halfspaces [abstract] [pdf]
    I. Diakonikolas, P. Gopalan, R. Jaiswal, R. Servedio, E. Viola
    SIAM Journal on Computing, 39(8), 3441-3462 (2010)
    Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009)

  158. Improved Approximation of Linear Threshold Functions [abstract] [pdf]
    I. Diakonikolas, R. Servedio
    Computational Complexity, 22(3), 623-677 (2013)
    Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC 2009)

  159. Efficiently Testing Sparse $GF(2)$ Polynomials [abstract] [pdf]
    I. Diakonikolas, H. Lee, K. Matulef, R. Servedio, A. Wan
    Algorithmica, 61(3), 580-605 (2011)
    Proceedings of the 35th Intl. Colloquium on Automata, Languages and Programming (ICALP 2008)

  160. Succinct Approximate Convex Pareto Curves [abstract] [pdf]
    I. Diakonikolas, M. Yannakakis
    Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008)

  161. Testing for Concise Representations [abstract] [pdf]
    I. Diakonikolas, H. Lee, K. Matulef, K. Onak, R. Rubinfeld, R. Servedio, A. Wan
    Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007)
    Oded Goldreich's Choices #39

  162. Small Approximate Pareto Sets for Biobjective Shortest Paths and Other Problems [abstract] [pdf]
    I. Diakonikolas, M. Yannakakis
    SIAM Journal on Computing, 39(4), 1340-1371 (2009)
    Proceedings of the 10th Intl. Workshop on Approximation, Randomization, and Combinatorial Optimization (APPROX 2007)
    Honorable Mention, George Nicholson student paper competition INFORMS society, 2009

Thesis


Professional Activities

Recent Teaching

Advising